#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
typedef struct NodeList
{
	struct NodeList* next;
	int data;
}NodeList;

int main()
{
	printf("===约瑟夫环的链表实现===\n");
	//创建一个首元节点，这样做的好处是不用传二级指针来改变head为空的情况
	NodeList* head = (NodeList*)malloc(sizeof(NodeList));
	NodeList* tail=head;
	head->data = 1;
	head->next = NULL;
	int N = 0;
	int M = 0;
	printf("请输入人数和报到几出圈\n");
	scanf("%d %d", &N,&M);
	//尾插n-1个节点
	for (int i = 2; i <= N; i++)
	{
		NodeList* newnode=(NodeList*)malloc(sizeof(NodeList));
		newnode->data = i;
		tail->next = newnode;
		tail = newnode;
	}
	//形成循环链表
	tail->next = head;
	tail = head;
	//模拟报数
	printf("出圈顺序为：");
	while (tail->next != tail)
	{
		NodeList* prevtail=tail;
		for (int i = 1; i < M; i++)
		{
			 prevtail = tail;
			tail = tail->next;
		}
		printf("%d ", tail->data);
		prevtail->next = tail->next;
		tail = tail->next;
	}
	//当tail->next=tail时还有一个人没报数，所以单独打印他！
	printf("%d", tail->data);
	return 0;
}